package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * User:yxd
 * Date:2022-04-04
 * Time:21:11
 */
public class Map229 {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i ++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i]) + 1);
            }
        }
        int count = nums.length / 3;
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < nums.length;i ++){
            if(map.get(nums[i]) > count){
                set.add(nums[i]);
            }
        }
        for(int x : set){
            list.add(x);
        }
        return list;
    }
}
